//
//  StandardTraverse.h
//  GraphTheory
//
//  Created by 刘振舟 on 2024/5/30.
//

#ifndef StandardTraverse_h
#define StandardTraverse_h
#include <iostream>
#include <vector>
#include <functional>
#include <queue>

using namespace std;


class StandardTraverseSolution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        
        //        捕获列表[&]表示在lambda函数使用函数外变量时引用计数
        function<void (vector<vector<int>>&, vector<bool>&, size_t, int)> dfs = [&](vector<vector<int>> &isConnectedCopy, vector<bool> &visitedCopy, size_t count, int index) {
            for (int j = 0; j < count; ++j) {
                if (isConnectedCopy[index][j] == 1 && !visitedCopy[j]) {
                    visitedCopy[j] = true;
                    dfs(isConnectedCopy, visitedCopy, count, j);
                }
            }
        };
        
        size_t cities = isConnected.size();
        int provinces = 0;
        vector<bool> visited(cities);
        
        for (int i = 0; i < cities; ++i) {
            if (!visited[i]) {
                dfs(isConnected, visited, cities, i);
                ++provinces;
            }
        }
        return provinces;
    }
    
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        size_t n = graph.size();
        vector<int> color(n);
        
        function<bool (int)> safe = [&](int x) {
            if (color[x] > 0) {
                return color[x] == 2;
            }
            color[x] = 1;
            for (int j : graph[x]) {
                if (!safe(j)) {
                    return false;
                }
            }
            color[x] = 2;
            return true;
        };
        
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (safe(i)) {
                ans.push_back(i);
            }
        }
        return ans;
        
    }
    
    
    
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        size_t n = rooms.size();
        vector<bool> visited(n, false);
        int num = 0;
        
        function<void (int)> dfs = [&](int x) {
            visited[x] = true;
            ++num;
            
            for (auto& y : rooms[x]) {
                if (!visited[y]) {
                    dfs(y);
                }
            }
        };
        dfs(0);
        return n == num;
    }
    
    
    
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> next(2, vector<vector<int>>(n));
        for (auto& it : redEdges) {
            next[0][it[0]].push_back(it[1]) ;
        }
        for (auto& it : blueEdges) {
            next[1][it[0]].push_back(it[1]) ;
        }
        
        vector<vector<int>> dist(2, vector<int>(n, INT_MAX));
        dist[0][0] = 0;
        dist[1][0] = 0;
        queue<pair<int, int>> que;
        que.push({0, 0});
        que.push({1, 0});
        
        while (!que.empty()) {
            auto [t, x] = que.front();
            que.pop();
            
            for (auto& y : next[1-t][x]) {
                if (dist[1 - t][y] != INT_MAX) {
                    continue;
                }
                dist[1 - t][y] = dist[t][x] + 1;
                que.push({1 - t, y});
            }
        }
        
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = min(dist[0][i], dist[1][i]);
            if (ans[i] == INT_MAX) {
                ans[i] = -1;
            }
        }
        return ans;
        
    }
    
    
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int res = 0;
        unordered_map<int, int> memory;
        
        function<int(int)> dfs = [&](int cur) {
            if (cur == headID) {
                return 0;
            }
            
            if (!memory.count(cur)) {
                memory[cur] = dfs(manager[cur]) + informTime[manager[cur]];
            }
            return memory[cur];
        };
        
        for (int i = 0; i < n; ++i) {
            res = max(res, dfs(i));
        }
        return res;
    }
    
    
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : connections) {
            graph[edge[0]].push_back(make_pair(edge[1], 1));
            graph[edge[1]].push_back(make_pair(edge[0], 0));
        }
        
        function<int(int, int)> dfs = [&](int cur, int parent) {
            int res = 0;
            for (auto& edge : graph[cur]) {
                if (edge.first == parent) {
                    continue;
                }
                res += edge.second + dfs(edge.first, cur);
            }
            return res;
        };
        
        return dfs(0, -1);
    }
    
    
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> paths;
        vector<int> stk;
        size_t target = graph.size() - 1;
        
        function<void(int)> dfs = [&](int x) {
            if (x == target) {
                paths.push_back(stk);
                return;
            }
            for (auto& y : graph[x]) {
                stk.push_back(y);
                dfs(y);
                stk.pop_back();
            }
        };
        stk.push_back(0);
        dfs(0);
        return paths;
    }
    
    
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        int* low = new int[n], * time = new int[n], idx = 0;
        memset(low, 0, n * sizeof(int));
        memset(time, 0, n * sizeof(int));
        vector<vector<int>> graph(n);
        for (int i = 0; i < connections.size(); ++i) {
            int x = connections[i][0], y = connections[i][1];
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        vector<vector<int>> ans;
        function<void(int, int)> dfs = [&](int cur, int parent) {
            low[cur] = time[cur] = ++idx;
            for (int child : graph[cur]) {
                if (time[child] == 0) {
                    dfs(child, cur);
                    low[cur] = min(low[cur], low[child]);
                    if (low[child] > time[cur]) {
                        ans.push_back({cur, child});
                    }
                } else if (time[child] < time[cur] && child != parent) {
                    low[cur] = min(time[child], low[cur]);
                }
            }
        };
        
        dfs(0, -1);
        delete[] low;
        delete[] time;
        return ans;
    }


    bool canReach(vector<int>& arr, int start) {
        if (arr[start] == 0)
            return true;
        queue<int> que;
        que.push(start);
        size_t size = arr.size();
        vector<bool> visited(size, false);
        visited[start] = true;

        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            if (arr[cur] == 0)
            {
                return true;
            }
            int tmp = cur + arr[cur];
            if (tmp < size && !visited[tmp]) {
                visited[tmp] = true;
                que.push(tmp);
            }
            tmp = cur - arr[cur];
            if (tmp >= 0 && !visited[tmp]) {
                visited[tmp] = true;
                que.push(tmp);
            }
        }
        return false;

    }
};

#endif /* StandardTraverse_h */
